/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-03-28
 * Time: 23:15
 */
public class TestDemo {


    class Solution {
        public void sortColors(int[] nums) {

            // left  指向数组的开始的位置，它指向的位置左侧都是 0
            int left = 0;

            // right  指向数组的结束的位置，它指向的位置右侧都是 2
            int right = nums.length - 1;

            // index 指向数组的开始位置
            int index = 0;

            // index 向后移动，当它越过 right 时跳出循环，不需要再判断了
            // 因为此时说明 index 右侧的都已经是 2
            while( index <= right ){

                // 获取当前的元素值
                int cur = nums[index];

                // 如果 index 位置上的元素值为 0
                if(cur == 0){
                    // 说明是红色，要放在最前面去
                    // 最前面的那个元素被 left 指着，所以让 index 指向的元素和 left 指向位置上的元素进行交换
                    swap(nums,left,index);

                    // index 可以向后移动
                    index++;

                    // left 可以向后移动，它的左侧区域都是 0
                    left++;

                    // 如果 index 位置上的元素值为 1
                }else if(cur == 1){
                    // 说明是白色，就应该放在中间，不用管它，继续移动 index
                    index++;

                    // 如果 index 位置上的元素值为 2
                }else if(cur == 2){

                    // 说明是蓝色，要放在最后面
                    // 所以让 index 指向的元素和 right 指向位置上的元素进行交换
                    swap(nums,right,index);

                    // 由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种
                    // 交换到了 index 后，还需要继续观察一轮，所以 index 先不移动
                    right--;
                }
            }

        }

        // 通过中间变量，交换两个元素的值
        // nums[i] 的值变为了 nums[j] 的值
        // nums[j] 的值变为了 nums[i] 的值
        private void swap(int[] nums, int i ,int j){
            // 使用临时变量 temp，保存 nums[i] 的值
            int temp = nums[i];

            // nums[i] 的值修改为 nums[j] 的值
            nums[i] = nums[j];

            // nums[i] 的值修改为 temp 的值
            nums[j] = temp;
        }
    }

    public static void main(String[] args) {

    }
}
